package com.ddshuai.easy;

/**
 * 描述 新通教育
 *
 * @author ddshuai
 * @date 2018-10-16 16:19
 **/
public class MySqrt {

    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int start = 1;
        int max = x >= 46340 ? 46340 : x;
        int middle;
        while (true) {
            middle = (start + max) / 2;
            int num = (start + max) / 2;
            int sqrt = num * num;
            int stepSqrt = (num + 1) * (num + 1);
            if (sqrt < x && stepSqrt > x) {
                return num;
            } else if (sqrt == x ) {
                return num;
            } else if (stepSqrt == x || (num + 1) == 46340) {
                return num + 1;
            } else {
                //小了 继续往前找
                if (sqrt < x && stepSqrt < x) {
                    start = middle;
                } else if (sqrt > x) {
                    //大了 往后找
                    max = middle;
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(2147483647));
        System.out.println(Math.sqrt(2147483647));
        System.out.println(mySqrt(25));
        System.out.println(Math.sqrt(25));
        System.out.println(mySqrt(16));
        System.out.println(Math.sqrt(16));
        System.out.println(mySqrt(10));
        System.out.println(Math.sqrt(10));
    }
}
